from collections import deque

"""
广度遍历是一种逐层访问节点的算法。它从根节点开始，先访问所有相邻的节点，然后再逐层向外扩展，直到访问完所有节点。
BFS通常使用队列（Queue）来实现。
"""


def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

    return result


if __name__ == "__main__":
    # 示例图（使用邻接表表示）
    _graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }

    print(bfs(_graph, 'A'))  # 输出: ['A', 'B', 'C', 'D', 'E', 'F']
